package summary;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @Author: 海琳琦
 * @Date: 2022/4/20 16:59
 * https://leetcode-cn.com/problems/matchsticks-to-square/
 */
public class Title473 {

    public static boolean makesquare(int[] matchsticks) {
        int L;
        int sum = 0;
        for (int i = 0; i < matchsticks.length; i++) {
            sum += matchsticks[i];
        }
        L = sum / 4;
        if (L * 4 != sum) {
            return false;
        }
        List<Integer> sticks = new ArrayList<>();
        for (int i = 0; i < matchsticks.length; i++) {
            sticks.add(matchsticks[i]);
        }
        Collections.sort(sticks, (a, b) -> (Integer.compare(b, a)));
        //存储四个边的值
        int[] nums = new int[4];
        return dfs(sticks, L, nums, 0);
    }

    private static boolean dfs(List<Integer> sticks, int L, int[] nums, int cur) {
        if (cur == sticks.size()) {
            if (nums[0] == L && nums[0] == nums[1] && nums[1] == nums[2] && nums[2] == nums[3]) {
                return true;
            }
            return false;
        }
        //将当前的火柴随意加到4个边当中
        for (int i = 0; i < 4; i++) {
            //nums[i] == nums[i-1]时，如果nums[i-1]不能放，则nums[i]如果放此火柴也同样会出现失败
            if (nums[i] + sticks.get(cur) > L || (i > 0 && nums[i] == nums[i - 1])) {
                continue;
            }
            nums[i] += sticks.get(cur);
            if (dfs(sticks, L, nums, cur + 1)) {
                return true;
            }
            nums[i] -= sticks.get(cur);
        }
        return false;
    }



    public static boolean makesquare2(int[] matchsticks) {
        int sum = 0;
        int n = matchsticks.length;
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            sum += matchsticks[i];
            list.add(matchsticks[i]);
        }
        if (sum % 4 != 0) {
            return false;
        }
        Collections.sort(list, (a, b) -> (b.compareTo(a)));
        int target = sum / 4;
        int[] arr = new int[4];
        return dfs(list, arr, n, target,0);
    }

    private static boolean dfs(List<Integer> matchsticks, int[] arr, int n, int target, int cur) {
        if (cur == n) {
            return true;
        }
        for (int i = 0; i < 4; i++) {
            if (arr[i] + matchsticks.get(cur) > target || (i != 0 && arr[i] == arr[i - 1])) {
                continue;
            }
            arr[i] += matchsticks.get(cur);
            if (dfs(matchsticks, arr, n, target, cur + 1)) {
                return true;
            }
            arr[i] -= matchsticks.get(cur);
        }
        return false;
    }


    public static void main(String[] args) {
        int[] matchsticks = {1, 1, 2, 2, 2};
        makesquare2(matchsticks);
    }

}
